// 递归搜索与回溯 - 决策树问题
// 当一个题目可以使用决策树画出来，那么也可以通过递归的方法解决
// 画决策树，要保证不重不漏，实际上就是暴搜
// 使用全局变量进行统计，避免递归函数头传参问题
// 设计递归函数头，是否需要记录本次决策的位置，层数，个数等信息
// 回溯时注意本层计算完成后，直接在本层回溯，返回上一个位置
// 经典题目：全排列，子集

// 例题 7：
// 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，
// 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
// candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
// 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
//
//        示例 1：
//
//        输入：candidates = [2,3,6,7], target = 7
//        输出：[[2,2,3],[7]]
//        解释：
//        2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
//        7 也是一个候选， 7 = 7 。
//        仅有这两种组合。
//        示例 2：
//
//        输入: candidates = [2,3,5], target = 8
//        输出: [[2,2,2,2],[2,3,3],[3,5]]
//        示例 3：
//
//        输入: candidates = [2], target = 1
//        输出: []
//
//
//        提示：
//
//        1 <= candidates.length <= 30
//        2 <= candidates[i] <= 40
//        candidates 的所有元素 互不相同
//        1 <= target <= 40

// 解题思路：
// 解法一：每次选择 candidate 中的一个数字
// 每次按顺序选择数组中 pos 位置的数字
// sum < target, 继续递归，返回本层时注意回溯
// sum == target, 收集结果
// sum > target, 返回（剪枝）

// 解法二： 从前往后，每个数字依次选 0 ~ i 次
// 每次按选择数组中 pos 位置的数字 0 ~ i 次
// 下次选 pos + 1 位置的数字 0 ~ i 次
// sum < target, 继续递归，本层结束时才回溯
// sum == target, 收集结果
// sum > target, 返回（剪枝）

import java.util.ArrayList;
import java.util.List;

public class CombinationSum {
    List<List<Integer>> ret;
    List<Integer> path;
    int sum;
    int n;
    public List<List<Integer>> combinationSum1(int[] candidates, int target) {
        n = candidates.length;
        sum = 0;
        path = new ArrayList<>();
        ret = new ArrayList<>();
        //Arrays.sort(candidates);
        dfs1(candidates, target, 0);
        return ret;
    }
    public void dfs1(int[] candidates, int target, int pos){
        if(sum == target){
            ret.add(new ArrayList(path));
            return;
        }
        for(int i = pos; i < n; i++){
            if(sum < target){
                sum += candidates[i];
                path.add(candidates[i]);
                dfs1(candidates, target, i);
                sum -= candidates[i];
                path.remove(path.size() - 1);
            }
        }
    }

    int t = 0;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        t = target;
        dfs2(candidates, 0, 0);
        return ret;
    }
    public void dfs2(int[] candidates, int pos, int sum){
        if(sum == t){
            ret.add(new ArrayList<>(path));
            return;
        }
        if(sum > t || pos == candidates.length) return;
        for(int i = 0; sum + candidates[pos] * i <= t; i++){
            if(i != 0)
                path.add(candidates[pos]);
            dfs2(candidates, pos + 1, sum + i * candidates[pos]);
        }
        for(int i = 1; sum + candidates[pos] * i <= t; i++){
            path.remove(path.size() - 1);
        }
    }
}
